1. Field of the Invention
The present invention relates to a method and apparatus for using a hardware hashing circuit to hash the input of a content addressable memory (CAM) array, thereby emulating a wider CAM array.
2. Related Art
Networking equipment (e.g., Internet routers) typically receive packets that include flow-based character strings, which identify the manner in which the associated packets should be routed. One example of such a flow-based character string includes a source IP address, a source port, a destination IP address and a destination port. In accordance with the IPv4 protocol, this flow-based character string has a length of 96-bits. In accordance with the Ipv6 protocol, this flow-based character string would have a length of 288-bits. Networking equipment also typically stores a reference list of flow-based character strings, along with corresponding routing information indicating the manner in which the packets are to be routed. Upon receiving a flow-based character string, the networking equipment must search its reference list of flow-based character strings in order to determine whether the received flow-based character string matches one of the flow-based character strings stored in the reference list. Upon matching the received flow-based character string with a flow-based character string stored in the reference list, the networking equipment is able to retrieve routing information associated with the received flow-based character string, and use this routing information to forward the associated packet. It is therefore desirable to be able perform a search for long character strings within networking equipment. It is also desirable for these searches to be completed as quickly as possible.
One conventional search method is to search data organized in a binary tree in a serial manner. However, if a million entries are organized in a binary tree, then recognizing a particular entry would take at least log2(106) steps (i.e., 20 steps). Thus, such a search method is relatively slow.
Another conventional search method is to search using a content addressable memory (CAM) array. However, CAM arrays typically have a relatively small width. For example, a conventional CAM array may have a width of 72-bits. This width is not large enough to accommodate all required searches. Thus, some CAM arrays are configured to store a single character string in a plurality of entries in the CAM array, thereby emulating a wider CAM array. For example, a CAM array having a width of 72-bits may store a character string having a width of 576-bits data in eight different entries of the CAM array (72×8=576). In this case, a 576-bit character string would be divided into eight 72-bit strings, and each of these eight 72-bit strings would have to be compared with the contents of the CAM array in order to detect a match. However, searching a plurality of entries causes this search method to be relatively slow. Moreover, storing a single character string in a plurality of entries of the CAM array effectively reduces the depth of the CAM array (because fewer character strings can be stored in this manner).
It would therefore be desirable to have a method and apparatus for using a CAM array to emulate a relatively wide CAM array, without reducing the operating speed of the CAM array, or reducing the effective depth of the CAM array.